package com.lc.boxuegu.H_maxSlidingWindow;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author zhaiyj
 * @date 2025/7/1 20:51
 */
public class Solution {

    public static void main(String[] args) {
        int[] nums = new int[]{1,3,-1,-3,5,3,6,7};
        Solution solution = new Solution();
        int[] ints = solution.maxSlidingWindow(nums, 3);
        System.out.println(ints);
    }

    public int[] maxSlidingWindow(int[] nums, int k) {

        int n = nums.length;
        int[] ans = new int[n - k + 1];
        Deque<Integer> q = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // 右边入
            while (!q.isEmpty() && nums[q.getLast()] <= nums[i]){
                q.removeLast();
            }
            q.addLast(i);

            // 左边出
            if(q.getFirst() <= i - k){// 队首已经离开窗口了
                q.removeFirst();
            }

            // 记录答案
            if(i >= k - 1){
               ans[i-k+1] = nums[q.getFirst()];
            }
        }
        return ans;
    }

    // 逻辑正常，但是未AC
    public int[] maxSlidingWindow1(int[] nums, int k) {
        if (k == 1) {
            return nums;
        }
        int start = 0;
        int end = start + k - 1;
        int[] result = new int[nums.length - k + 1];
        while (end < nums.length) {
            int max = Integer.MIN_VALUE;
            for (int i = start; i <= end; i++) {
                max = Math.max(max, nums[i]);
            }
            result[start] = max;
            start++;
            end++;
        }
        return result;
    }


}
